class: center, middle, inverse, title-slide .title[ # APEC8003: Recitation 5 ] .author[ ### Shunkei Kakimoto ] --- class: middle <style type="text/css"> <!-- center figure --> .center2 { margin: 0; position: absolute; top: 50%; left: 50%; -ms-transform: translate(-50%, -50%); transform: translate(-50%, -50%); } .small-code .remark-code{ font-size: 50% } .medium-code .remark-code{ font-size: 70% } .xlarge { font-size: 150% } .large { font-size: 130% } .medium { font-size: 80% } .small { font-size: 70% } .xsmall { font-size: 50% } <!-- .remark-slide-number { font-size: 10pt; margin-bottom: -11.6px; margin-right: 10px; color: red; /* white */ opacity: 1; /* default: 0.5 */ } --> .remark-slide-number { font-size: 12pt; right: 5%; color: black; /* white */ } .one-page-font { font-size: 14px; } .remark-slide-content.hljs-github h1 { margin-top: 5px; margin-bottom: 25px; } .remark-slide-content.hljs-github { padding-top: 10px; padding-left: 30px; padding-right: 30px; } .panel-tabs { <!-- color: #062A00; --> color: #841F27; margin-top: 0px; margin-bottom: 0px; margin-left: 0px; padding-bottom: 0px; } .panel-tab { margin-top: 0px; margin-bottom: 0px; margin-left: 3px; margin-right: 3px; padding-top: 0px; padding-bottom: 0px; } .panelset .panel-tabs .panel-tab { min-height: 40px; } .remark-slide th { border-bottom: 1px solid #ddd; } .remark-slide thead { border-bottom: 0px; } .gt_footnote { padding: 2px; } .remark-slide table { border-collapse: collapse; } .remark-slide tbody { border-bottom: 2px solid #666; } .important { background-color: lightpink; border: 2px solid blue; font-weight: bold; } .remark-code { display: block; overflow-x: auto; padding: .5em; background: #ffe7e7; } .remark-code, .remark-inline-code { font-family: 'Source Code Pro', 'Lucida Console', Monaco, monospace;font-size: 90%; } .hljs-github .hljs { background: #f2f2fd; } .remark-inline-code { padding-top: 0px; padding-bottom: 0px; background-color: #e6e6e6; } .r.hljs.remark-code.remark-inline-code{ font-size: 0.9em } .left-full { width: 80%; float: left; } .left-code { width: 38%; height: 92%; float: left; } .right-plot { width: 60%; float: right; padding-left: 1%; } .left6 { width: 60%; height: 92%; float: left; } .left5 { width: 49%; <!-- height: 92%; --> float: left; } .right5 { width: 49%; float: right; padding-left: 1%; } .right4 { width: 39%; float: right; padding-left: 1%; } .left3 { width: 29%; height: 92%; float: left; } .right7 { width: 69%; float: right; padding-left: 1%; } .left4 { width: 38%; float: left; } .right6 { width: 60%; float: right; padding-left: 1%; } ul li{ margin: 7px; } ul, li{ margin-left: 15px; padding-left: 0px; } ol li{ margin: 7px; } ol, li{ margin-left: 15px; padding-left: 0px; } </style> <style type="text/css"> .content-box { box-sizing: border-box; background-color: #e2e2e2; } .content-box-blue, .content-box-gray, .content-box-grey, .content-box-army, .content-box-green, .content-box-purple, .content-box-red, .content-box-yellow { box-sizing: border-box; border-radius: 5px; margin: 0 0 10px; overflow: hidden; padding: 0px 5px 0px 5px; width: 100%; } .content-box-blue { background-color: #F0F8FF; } .content-box-gray { background-color: #e2e2e2; } .content-box-grey { background-color: #F5F5F5; } .content-box-army { background-color: #737a36; } .content-box-green { background-color: #d9edc2; } .content-box-purple { background-color: #e2e2f9; } .content-box-red { background-color: #ffcccc; } .content-box-yellow { background-color: #fef5c4; } .content-box-blue .remark-inline-code, .content-box-blue .remark-inline-code, .content-box-gray .remark-inline-code, .content-box-grey .remark-inline-code, .content-box-army .remark-inline-code, .content-box-green .remark-inline-code, .content-box-purple .remark-inline-code, .content-box-red .remark-inline-code, .content-box-yellow .remark-inline-code { background: none; } .full-width { display: flex; width: 100%; flex: 1 1 auto; } </style> <style type="text/css"> blockquote, .blockquote { display: block; margin-top: 0.1em; margin-bottom: 0.2em; margin-left: 5px; margin-right: 5px; border-left: solid 10px #0148A4; border-top: solid 2px #0148A4; border-bottom: solid 2px #0148A4; border-right: solid 2px #0148A4; box-shadow: 0 0 6px rgba(0,0,0,0.5); /* background-color: #e64626; */ color: #e64626; padding: 0.5em; -moz-border-radius: 5px; -webkit-border-radius: 5px; } .blockquote p { margin-top: 0px; margin-bottom: 5px; } .blockquote > h1:first-of-type { margin-top: 0px; margin-bottom: 5px; } .blockquote > h2:first-of-type { margin-top: 0px; margin-bottom: 5px; } .blockquote > h3:first-of-type { margin-top: 0px; margin-bottom: 5px; } .blockquote > h4:first-of-type { margin-top: 0px; margin-bottom: 5px; } .text-shadow { text-shadow: 0 0 4px #424242; } </style> <style type="text/css"> /****************** * Slide scrolling * (non-functional) * not sure if it is a good idea anyway slides > slide { overflow: scroll; padding: 5px 40px; } .scrollable-slide .remark-slide { height: 400px; overflow: scroll !important; } ******************/ .scroll-box-8 { height:8em; overflow-y: scroll; } .scroll-box-10 { height:10em; overflow-y: scroll; } .scroll-box-12 { height:12em; overflow-y: scroll; } .scroll-box-14 { height:14em; overflow-y: scroll; } .scroll-box-16 { height:16em; overflow-y: scroll; } .scroll-box-18 { height:18em; overflow-y: scroll; } .scroll-box-20 { height:20em; overflow-y: scroll; } .scroll-box-24 { height:24em; overflow-y: scroll; } .scroll-box-30 { height:30em; overflow-y: scroll; } .scroll-output { height: 90%; overflow-y: scroll; } </style> # Where are we? <img src="data:image/png;base64,#photos/game_types.png" width="100%" style="display: block; margin: auto;" /> ??? + Okay, let's get started. We are about to finish week 5 of the first quater of the spring semester, and there are only two weeks left. + This week, we finished static game of incomplete infromation and we started to dive into the Dybamic games of incomlete information. + Depending on the types of game, we have different kinds of Nash Equilibrium. + But the fundamental characteristic of these equilibria is the same. + That is, "At equilibrium, each player's strategy is the best response to the other players' strategies." + This is the key thing that you might want to always keep in your mind. + By the way, do you remember the meaning of incomplete infomration? + incomplete infomration means players do not have full information about their opponents. + In the case of signiling game, a signal reciever has a private information about their types, and signal reciever does not have such an information. + What about perfect information? + if not all information sets are single ton. Or, at least one player at some point in the game tree does not know where they are in the tree --- class: middle # Overview: Signaling game Players: a signal sender (e.g., employee) and a signal receiver (e.g., employer) .bg-washed-green.b--dark-green.ba.bw2.br3.shadow-2.ph2.mt2[ **step 1** Pick a strategy for sender (seprarating or pooling stratgy). Assume it is sender's strategy at equilibirum. + <span style="color:blue">We want to check whether this sender's strategy can be a part of PBE or not</span> **step 2** What's the receiver's beliefs about sender's type that are consistent with the sender's strategy? Given that belief, what's the receiver's BR? **step 3** Given the receiver's BR, what's the sender's BR? Is it consistent with what we assumed for this equilibrium? (or can you find any profitable deviation for player 1 that what we assumed in step 1?) + If it is consistent, it is a pure strategy PBE. + If no, there is no pure strategy PBE as such. **step 4** Check whether the PBE satisfy intuitive criteria (not for today. We'll learn this in the next lecture). ] Repeat step 1 ~ step 4 for all possible player 1's strategies. ??? + Okay, today, I wanna talk about signaling game. + Do you guys remember what the game looks like? + I will try as much as possible to walk through the steps to solve the problem with my small brain. + Here, I summarised steps to solve the problem. + In signaling game, there are two players, a signal sender, and a singnal receiver. + First, the nature determies the type of the sender which is private infromation. Then, sender send a signal. Given tht signal, reciever determines their action. + The basic flow and logic are the follwings. + The first step is to pick a potential strategy for player 1, and assume it consists of PBE. + This part is not difficult. What we want to do for the rest of the step is to check whether the assumed palyer 1's strategy consists of PBE or not. + In Step 2, we define player 2's belief about player 1's type, and given that belief, derive Player 2's BR. + In step 3, --- class: middle ## "Practice makes perfect" Let's do it! ??? + "Practice makes perfect". + Maybe you guys don't understand what I am talking about, so let's paractice. + Also, as you will see when you review the past final exam, the same type of the question is asked every year in Problem 1, and you don't want to spend lots of time in the first problem. + So, let's practice how to solve signaling game. --- class: middle # Spring 2023 Finall Problem 1 Consider the following signaling game shown in the figure below, where player 1 can be of two types and chooses to play `\(L\)` or `\(R\)`. Player 2 initially does not know whether player 1 is of type `\(t1\)` or type `\(t2\)`, only the initial probabilities. Player 2 observes the choice of L or R and may update probabilities of types based on the choice by player 1. Player 2 then chooses `\(U\)` or `\(D\)`. <img src="data:image/png;base64,#photos/ex1.png" width="60%" style="display: block; margin: auto;" /> a. Find all pure strategy perfect Bayesian equilibria for this game. <br> Problem 1 has three questions. Next week, we will work on questions (b) and (c). Question (b) is related to the intuitive criterion. ??? + Let's practive using the problem 1 from last year's exam. + This is a typical signaling game. Player 1 chooses either left or rigt. Player 2 can ovserve player 1's choice and take as a signal, and choose either upp or down. --- class: middle # Set up I will use the following notations. <img src="data:image/png;base64,#photos/setup.png" width="60%" style="display: block; margin: auto;" /> Define: Player 2's belief: `\(p=Pr[t_1|L]\)` and `\(q=Pr[t_1|R]\)` Player 1's strategy: `\((s_1^{t1}, s_1^{t2})\)`, Player 2's strategy: `\((s_2^{L}, s_2^{R})\)` ??? + I will use the following notations. `\(p\)` and `\(q\)` are the player 2's belief (in terms of probability) about player 1's type given player 1's signal. For example, `\(p\)` is the player 2's belief that player 1 is type 1 after observing player 1 plays L. ??? + Before we start, let me define some math notations just for my convenience. + For player 2's beliefs, I'm gonna use `\(p\)` to denote the probability that the player 1's type is 1 after seeing L, and `\(q\)` to to denote the probability that the playr 1's type is 2 after seeing R. + These are player 1 and player 2's strategies. + This means player 2's strategy upon observing L, and this means player 2's strategy upon observing R. --- class: middle step 0: Write out the possible strategies for player 1 (signal sender). ??? + Let's start with this. Since we need to assume player 1's potential strategy at equilibirium in step 1, we want need to know the set of strategies for player 1. + We have two nodes that does not share the information set here. So, we need to specify player 1's strategies for type 1 and and type 2, respectively. --- class: middle step 0: Write out the set of strategies for player 1 (signal sender). Player 1's strategy: `$$(s_1^{t_1}, s_1^{t_2}) \in \{\underbrace{(L, R), (R, L)}_\text{Separating strategies}, \underbrace{(L, L), (R, R)}_\text{Pooling strategies}\}$$` ??? + This is the set of strategies for player 1. + In other words, there are four possible pure strategy PBE, where two are for pooling equilibrium and the other two are for separating equilibrium. + Examing a separating equlibirium is easier than examining a pooling equilibirum. So, let's start with a separating equilibrium. + After I explained the first separating equilibrium, I let you guys reactice for the second separating equilibrium. --- class: middle ## Case I: Separating Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, R)\)` <b>Step 1:</b> Suppose that player 1 plays a separating strategy `\((s_1^{t_1}, s_1^{t_2})=(L, R)\)` at equilibrium. <img src="data:image/png;base64,#photos/I_1.png" width="80%" style="display: block; margin: auto;" /> <b>Step 2:</b> What should player 2's beliefs be? What is the player 2's BR to Player 1's strategy? Player 2's beliefs are `\(p=1\)` and `\(q=0\)`. Given these beliefs, player 2's BR is `\((s_2^{L}, s_2^{R})=(D, D)\)`. ??? + Step 1, we assume that ... + The blue line shows the assumed player 1's strategy. + Then in step2, given the separating sestrategy of player 1, we need to specifcy the player 2's beliefs, and his BR to player 1's strategy. + What should player 2's belief be? + --- class: middle ## Case I: Separating Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, R)\)` We found that player 2's BR is `\((s_2^{L}, s_2^{R})=(D, D)\)`. <img src="data:image/png;base64,#photos/I_2.png" width="80%" style="display: block; margin: auto;" /> --- class: middle ## Case I: Separating Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, R)\)` <img src="data:image/png;base64,#photos/I_3.png" width="60%" style="display: block; margin: auto;" /> <b>Step 3:</b> Given player 2's BR, what is player 1's BR? Is it consistent with what we assumed for this equilibrium? + Player 1's BR is `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` (oops, type 2 would rather play `\(L\)` than `\(R\)`!) **Conclusion**: There is no separating equilibrium as such. ??? + The next question is what is player 1's BR given player 2's BR. + For type 1, we compare player 1's payoff of 1 by playing L, and payoff of 0 obtained by playing R. Obviously, --- class: middle ## Case II: Separating Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(R, L)\)` Let's practice. Find a pure strategy PBE for this case. <img src="data:image/png;base64,#photos/I_4.png" width="70%" style="display: block; margin: auto;" /> ??? + You should get `\(\{R,L; U, U; p=0, q=1\}\)` --- ## Memo: --- class: middle ## Case III: Pooling Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` <b>Step 1:</b> Suppose that player 1 plays a pooling strategy `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` at equilibrium. <img src="data:image/png;base64,#photos/I_5.png" width="70%" style="display: block; margin: auto;" /> <b>Step 2:</b> Player 2's beliefs are `\(p=0.5\)` and `\(q \in [0,1]\)`. Given these beliefs, what is Player 2's BR to Player 1's strategy? --- class: middle ## Case III: Pooling Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` <img src="data:image/png;base64,#photos/I_6.png" width="70%" style="display: block; margin: auto;" /> .content-box-green[If player 1 plays L] `\begin{align*} \text{Player 2's expected payoffs} = \begin{cases} 0 \cdot 1/2 + 1 \cdot 1/2 = 1/2 &\quad \text{by playing U} \\ 2 \cdot 1/2 + 0 \cdot 1/2 = 1 &\quad \text{by playing D} \end{cases} \end{align*}` So, player 2's BR when player 1 plays L is `\(s_2^{L}=D\)` --- class: middle ## Case III: Pooling Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` <img src="data:image/png;base64,#photos/I_7.png" width="70%" style="display: block; margin: auto;" /> .content-box-green[If player 1 plays R] `\begin{align*} \text{Player 2's expected payoffs} = \begin{cases} 2 \cdot q + 0 \cdot (1-q) = 2q &\quad \text{by playing U} \\ 0 \cdot q + 1 \cdot (1-q) = 1-q &\quad \text{by playing D} \end{cases} \end{align*}` So, `\begin{align*} \text{Player 2's BR correspondence} = \begin{cases} U \quad & \text{ if } \, q > 1/3 \\ U \text{ or } D &\text{ if } \, q = 1/3 \\ D &\text{ if } \, q < 1/3 \end{cases} \end{align*}` --- class: middle ## Case III: Pooling Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(L, L)\)` <img src="data:image/png;base64,#photos/I_8.png" width="80%" style="display: block; margin: auto;" /> <b>Step 3:</b> Given Player 2's BR, what is Player 1's BR? Any profitable deviation from what we assumed? + For type 1, playing `\(L\)` yields payoff of `\(1\)`. <span style="color:blue">But, type 1 can get higher payoff of 3 by playing `\(R\)` (if player 2's belief is `\(q > 1/3\)`). Playing `\(L\)` is type 1's BR if `\(q \leq 1/3\)`</span> + Similarly, for type 2, playing `\(L\)` is the BR if `\(q \leq 1/3\)`. **Conclusion**: Thus, PBE is `\(\{L, L; D, D; p=0.5, q \leq 1/3 \}\)` --- class: middle ## Case IV: Pooling Equilibrium `\((s_1^{t_1}, s_1^{t_2})=(R, R)\)` Let's practice. Find a pure strategy PBE for this case. <img src="data:image/png;base64,#photos/I_9.png" width="70%" style="display: block; margin: auto;" /> ??? + You should get `\(\{R,R; D, U; p\ge1/3, q=0.5\}\)` --- ## Memo: ---